Модуларна аритметика
Кажемо да је број \(r\) остатак при дељењу броја \(x\) бројем \(y\) и пишемо \(x\,\mathrm{mod}\,y = r\) ако и само ако постоји број \(q\) такав да је \(x = q\cdot y + r\) и \(0 \leq r < y\). Поред тога што са \(\,\mathrm{mod}\,\) означавамо бинарну операцију, \(\,\mathrm{mod}\,\) се може користити и као ознака бинарне релације у скупу целих бројева. Наиме, писаћемо \(a\equiv b \,\mathrm{mod}\,m\) ако \(m|(a-b)\). Ово је еквивалентно томе да \(a\) и \(b\) дају исти остатак при дељењу са \(m\). На пример, пишемо \(12\equiv 2 \,\mathrm{mod}\,5\) јер \(5|(12-2)\).
Релацију \(\,\mathrm{mod}\,\) користимо у неким свакодневним ситуацијама, а да тога често нисмо ни свесни.
Један од таквих примера је рад са временом. Наиме, за 15 сати након 11 часова рећи ћемо да је 2 сата (што одговара томе да је \(11+15 \equiv 2 \,\mathrm{mod}\,{24}\)).
Слично важи и за дане у недељи, које рачунамо по модулу 7. Ако је данас, рецимо, четвртак и интересује нас који ће дан бити за сто дана, не морамо да бројимо један по један дан. Сваком дану можемо придружити неки остатак при дељењу са 7 (0 - понедељак, 1 - уторак, 2 - среда, 3 - четвртак, 4 - петак, 5 - субота, 7 - недеља), а затим израчунати \((3 + 100) \,\mathrm{mod}\,7 = 5\) и знаћемо да је за 100 дана субота (проћи ће 14 пуних недеља тј. 98 дана и биће поново четвртак, након 99 дана ће бити петак, а након 100 субота). Аналогно се рачуна и месец или редни број недеље у години.
Слично важи и приликом рада са угловима (које рачунамо по модулу 360 степени).
Модуларна аритметика има пуно практичних примена: користи се за израчунавање контролних сума за међународне стандардне идентификаторе књига (ISBN бројеве) и идентификаторе банки (IBAN). Модуларна аритметика је и у основи савремених криптографских система.
Бројеви се у рачунарима представљају по модулу \(2^k\). На пример, у
језику C++ бројеви типа unsigned int представљају се по
модулу \(2^{32}\).
На пример, у језику C# бројеви типа
uint представљају се по модулу \(2^{32}\). У наредном
коду резултат квадрирања броја \(123456789\) биће вредност \(123456789^2 \,\mathrm{mod}\,32 =
2537071545\).
unsigned int x = 123456789;
cout << x*x << endl;Сабирање и множење по модулу
Уколико је потребно одредити вредност збира или производа бројева по модулу \(m\) од помоћи нам могу бити наредне релације:
\[(a + b)\,\mathrm{mod}\,m = (a\,\mathrm{mod}\,m\ +\ b\,\mathrm{mod}\,m)\,\mathrm{mod}\,m\]
\[(a \cdot b)\,\mathrm{mod}\,m = (a\,\mathrm{mod}\,m\ \cdot\ b\,\mathrm{mod}\,m)\,\mathrm{mod}\,m\]
Доказ коректности. за доказивање, па је остављамо за вежбу). Претпоставимо да је \(a = q_a\cdot m + r_a\) и \(b = q_b\cdot m + r_b\) за \(0 \leq r_a, r_b < m\). Тада важи да је \(a\cdot b\) = \((q_a \cdot m + r_a) \cdot (q_b \cdot m + r_b)\) = \((q_a \cdot q_b \cdot m + q_a \cdot r_b + r_a\cdot q_b)m + r_a\cdot r_b\). Ако важи да је \(r_a \cdot r_b = q\cdot m + r\) за \(0 \leq r < m\), тада је са \(a\cdot b = (q_a \cdot q_b \cdot m + q_a \cdot r_b + r_a\cdot q_b + q)m + r\), па је \((a \cdot b)\,\mathrm{mod}\,m = r\). Са друге стране, важи да је \((a\,\mathrm{mod}\,m\ \cdot\ b \,\mathrm{mod}\,\ m)\,\mathrm{mod}\,m = (r_a \cdot r_b)\,\mathrm{mod}\,m = r,\) чиме је тврђење доказано.
Одузимање по модулу
Размотримо проблем одређивања разлике бројева \(b\) и \(a\) по модулу \(m\). На пример, потребно је одредити
вредност \((b-a)\,\mathrm{mod}\,m\).
Желели бисмо да као вредност овог израза добијемо ненегативну вредност
чак и у случају када је \(b < a\).
Међутим, не постоји сагласност између различитих програмских језика у
рачунању вредности x % m када је x негативно.
Наиме, у језику C++ и у језику C# бисмо за вредност остатка добили
негативан број: вредност израза (2 - 7) % 3 била би
-2, док би у језику Python као резутат добили позитиван
број 1. Уместо да вршимо испитивање да ли је дељеник
негативан, ако је \(0 \leq a, b <
m\), позитиван резултат је могуће добити израчунавањем вредности
израза \((b - a +
m)\,\mathrm{mod}\,m\). Додавањем вредности \(m\), вредност \(b
- a + m\) ће постати сигурно ненегативна (јер разлика \(b-a\) не може бити мања од \(-m\)), а тражење остатка ће практично
поништити првобитно додавање вредности \(m\)). У претходном смо се ослонили на
чињеницу да су и \(a\) и \(b\) бројеви који су већи или једнаки од
\(0\) и строго мањи од \(m\). Проналажење вредности разлике по
модулу \(m\) могуће је и у општем
случају и важи
\[(B - A)\,\mathrm{mod}\,m = (B\,\mathrm{mod}\,m - A\,\mathrm{mod}\,m + m)\,\mathrm{mod}\,m\]
Доказ коректности. Докажимо ово тврђење. Подсетимо се да је \(x\,\mathrm{mod}\,y = r\) ако и само ако постоји \(q\) такав да је \(x = q\cdot y + r\) и ако је \(0 \leq r < y\). Нека је \(A = q_a\cdot m + a\) и \(B = q_b\cdot m + b\), за \(0 \leq a, b < m\). Зато је \(A\,\mathrm{mod}\,m = a\) и \(B\,\mathrm{mod}\,m = b\). Нека је \(B - A + m = p\cdot m + r\) за неко \(0 \leq r < m\). Зато је \((B\,\mathrm{mod}\,m - A\,\mathrm{mod}\,m + m)\,\mathrm{mod}\,m = (b - a + m)\,\mathrm{mod}\,m = r\). Такође, важи и да је \(B-A = (q_b - q_a)\cdot m + (b - a) = (q_b - q_a - 1)\cdot m + (b - a + m) = (q_b - q_a - 1 + p)\cdot m + r\), па је и \((B-A)\,\mathrm{mod}\,m = r\), чиме је тврђење доказано.
Степеновање по модулу
Као последица множења по модулу, важи и наредно тврђење, које омогућава да се израчуна степен по модулу:
\[a^n \,\mathrm{mod}\,m = (a\,\mathrm{mod}\,m)^n \,\mathrm{mod}\,m\]
Модуларна аритметика
Кажемо да је број \(r\) остатак при дељењу броја \(x\) бројем \(y\) и пишемо \(x\,\mathrm{mod}\,y = r\) ако и само ако постоји број \(q\) такав да је \(x = q\cdot y + r\) и \(0 \leq r < y\). Поред тога што са \(\,\mathrm{mod}\,\) означавамо бинарну операцију, \(\,\mathrm{mod}\,\) се може користити и као ознака бинарне релације у скупу целих бројева. Наиме, писаћемо \(a\equiv b \,\mathrm{mod}\,m\) ако \(m|(a-b)\). Ово је еквивалентно томе да \(a\) и \(b\) дају исти остатак при дељењу са \(m\). На пример, пишемо \(12\equiv 2 \,\mathrm{mod}\,5\) јер \(5|(12-2)\).
Релацију \(\,\mathrm{mod}\,\) користимо у неким свакодневним ситуацијама, а да тога често нисмо ни свесни.
Један од таквих примера је рад са временом. Наиме, за 15 сати након 11 часова рећи ћемо да је 2 сата (што одговара томе да је \(11+15 \equiv 2 \,\mathrm{mod}\,{24}\)).
Слично важи и за дане у недељи, које рачунамо по модулу 7. Ако је данас, рецимо, четвртак и интересује нас који ће дан бити за сто дана, не морамо да бројимо један по један дан. Сваком дану можемо придружити неки остатак при дељењу са 7 (0 - понедељак, 1 - уторак, 2 - среда, 3 - четвртак, 4 - петак, 5 - субота, 7 - недеља), а затим израчунати \((3 + 100) \,\mathrm{mod}\,7 = 5\) и знаћемо да је за 100 дана субота (проћи ће 14 пуних недеља тј. 98 дана и биће поново четвртак, након 99 дана ће бити петак, а након 100 субота). Аналогно се рачуна и месец или редни број недеље у години.
Слично важи и приликом рада са угловима (које рачунамо по модулу 360 степени).
Модуларна аритметика има пуно практичних примена: користи се за израчунавање контролних сума за међународне стандардне идентификаторе књига (ISBN бројеве) и идентификаторе банки (IBAN). Модуларна аритметика је и у основи савремених криптографских система.
Бројеви се у рачунарима представљају по модулу \(2^k\). У наредном коду резултат квадрирања броја \(123456789\) биће вредност \(123456789^2 \,\mathrm{mod}\,32 = 2537071545\).
unsigned int x = 123456789;
cout << x*x << endl;Сабирање и множење по модулу
Уколико је потребно одредити вредност збира или производа бројева по модулу \(m\) од помоћи нам могу бити наредне релације:
\[(a + b)\,\mathrm{mod}\,m = (a\,\mathrm{mod}\,m\ +\ b\,\mathrm{mod}\,m)\,\mathrm{mod}\,m\]
\[(a \cdot b)\,\mathrm{mod}\,m = (a\,\mathrm{mod}\,m\ \cdot\ b\,\mathrm{mod}\,m)\,\mathrm{mod}\,m\]
Доказ коректности. за доказивање, па је остављамо за вежбу). Претпоставимо да је \(a = q_a\cdot m + r_a\) и \(b = q_b\cdot m + r_b\) за \(0 \leq r_a, r_b < m\). Тада важи да је \(a\cdot b\) = \((q_a \cdot m + r_a) \cdot (q_b \cdot m + r_b)\) = \((q_a \cdot q_b \cdot m + q_a \cdot r_b + r_a\cdot q_b)m + r_a\cdot r_b\). Ако важи да је \(r_a \cdot r_b = q\cdot m + r\) за \(0 \leq r < m\), тада је са \(a\cdot b = (q_a \cdot q_b \cdot m + q_a \cdot r_b + r_a\cdot q_b + q)m + r\), па је \((a \cdot b)\,\mathrm{mod}\,m = r\). Са друге стране, важи да је \((a\,\mathrm{mod}\,m\ \cdot\ b \,\mathrm{mod}\,\ m)\,\mathrm{mod}\,m = (r_a \cdot r_b)\,\mathrm{mod}\,m = r,\) чиме је тврђење доказано.
Одузимање по модулу
Размотримо проблем одређивања разлике бројева \(b\) и \(a\) по модулу \(m\). На пример, потребно је одредити
вредност \((b-a)\,\mathrm{mod}\,m\).
Желели бисмо да као вредност овог израза добијемо ненегативну вредност
чак и у случају када је \(b < a\).
Међутим, не постоји сагласност између различитих програмских језика у
рачунању вредности x % m када је x негативно.
Наиме, у језику C++ и у језику C# бисмо за вредност остатка добили
негативан број: вредност израза (2 - 7) % 3 била би
-2, док би у језику Python као резутат добили позитиван
број 1. Уместо да вршимо испитивање да ли је дељеник
негативан, ако је \(0 \leq a, b <
m\), позитиван резултат је могуће добити израчунавањем вредности
израза \((b - a +
m)\,\mathrm{mod}\,m\). Додавањем вредности \(m\), вредност \(b
- a + m\) ће постати сигурно ненегативна (јер разлика \(b-a\) не може бити мања од \(-m\)), а тражење остатка ће практично
поништити првобитно додавање вредности \(m\)). У претходном смо се ослонили на
чињеницу да су и \(a\) и \(b\) бројеви који су већи или једнаки од
\(0\) и строго мањи од \(m\). Проналажење вредности разлике по
модулу \(m\) могуће је и у општем
случају и важи
\[(B - A)\,\mathrm{mod}\,m = (B\,\mathrm{mod}\,m - A\,\mathrm{mod}\,m + m)\,\mathrm{mod}\,m\]
Доказ коректности. Докажимо ово тврђење. Подсетимо се да је \(x\,\mathrm{mod}\,y = r\) ако и само ако постоји \(q\) такав да је \(x = q\cdot y + r\) и ако је \(0 \leq r < y\). Нека је \(A = q_a\cdot m + a\) и \(B = q_b\cdot m + b\), за \(0 \leq a, b < m\). Зато је \(A\,\mathrm{mod}\,m = a\) и \(B\,\mathrm{mod}\,m = b\). Нека је \(B - A + m = p\cdot m + r\) за неко \(0 \leq r < m\). Зато је \((B\,\mathrm{mod}\,m - A\,\mathrm{mod}\,m + m)\,\mathrm{mod}\,m = (b - a + m)\,\mathrm{mod}\,m = r\). Такође, важи и да је \(B-A = (q_b - q_a)\cdot m + (b - a) = (q_b - q_a - 1)\cdot m + (b - a + m) = (q_b - q_a - 1 + p)\cdot m + r\), па је и \((B-A)\,\mathrm{mod}\,m = r\), чиме је тврђење доказано.
Степеновање по модулу
Као последица множења по модулу, важи и наредно тврђење, које омогућава да се израчуна степен по модулу:
\[a^n \,\mathrm{mod}\,m = (a\,\mathrm{mod}\,m)^n \,\mathrm{mod}\,m\]